package nextoffer;

import java.util.Arrays;

public class QuickSort {
    static class Solution {
        public int[] sortArray(int[] nums) {
            int left = 0, right = nums.length - 1;
            quick(nums, left, right);
            return nums;
        }

        public void quick(int[] nums, int l , int r) {
            if(l < r){
                int x = quickSort(nums, l, r);
                quick(nums, l, x - 1);
                quick(nums, x + 1, r);
            }
        }

        public int quickSort(int[] nums, int l, int r)  {
            int i = l, j = r;
            int x = nums[i];
            while(i < j) {
                while(i < j && nums[j] >= x) j--;
                swap(nums, i, j);
                while(i < j && nums[i] <= x) i++;
                swap(nums, i, j);
            }
            nums[i] = x;
            return i;
        }

        public void swap(int[] nums, int l, int r){
            int t = nums[l]; nums[l] = nums[r];nums[r] = t;
        }
    }

    public static void main(String[] args) {
        int[] ints = new Solution().sortArray(new int[]{5,1,1,2,0,0});
        Arrays.stream(ints).forEach(x -> System.out.println(x));

    }
}
